Corelab Seminar
2009-2010
Paris Koutris (NTUA)
Offline and Online Infrastructure Leasing Problems.
Abstract. Traditional infrastructure problems assume that the infrastructures weuse are permanent, i.e. that after the infrastructure is allocated, it can be used any time in the future. In this talk, a different modelis discussed, where we are allowed to lease infrastructures for fixedlengths of time instead of buying them permanently. We will firstintroduce the leasing variant of the well-studied ski-rental problem,the Parking Permit problem and present deterministic and randomizedalgorithms in the online setting. Next, we will show how theleasing model can be applied to problems such as Steiner Tree, Facility Location and Set Cover and study the relationship between infrastructure leasing problems and the notion of multistage stochastic optimization.